// 树
/**
 * 树节点
 */
class TreeNode {
    constructor(val) {
        this.childs = [];
        this.val = val;
    }

    /**
     * 添加子节点
     * @param ele
     */
    addChild(ele) {
        this.childs.push(ele);
    }

    /**
     * 判断是否为叶子节点
     * @returns {boolean}
     */
    isLeaf() {
        if (this.childs == null || this.childs.length <= 0) {
            return true;
        }
        return false;
    }
}

class Tree {
    constructor(node) {
        this.root = node;
    }

    /**
     * 获取树的深度
     * @returns {number}
     */
    treeHeight(node) {
        if (node == null) {
            return 0;
        }
        if (node.childs == null || node.childs.length == 0) {
            return 1;
        }
        let lastHeight = 0;
        for (let i = 0; i < node.childs.length; i++) {
            let height = 1 + this.treeHeight(node.childs[i]);
            if (height > lastHeight) {
                lastHeight = height;
            }
        }
        return lastHeight;
    }

    /**
     * 层序遍历
     */
    levelOrder(root) {
        if (root == null) {
            return;
        }
        let arr = [];
        arr.push(root);
        let level = 1;
        while (arr.length > 0) {
            console.log(`第${level}层`)
            let newArr = [];
            for (let i = 0; i < arr.length; i++) {
                let node = arr[i];
                console.log(node.val)
                let childs = node.childs;
                if (childs && childs.length > 0) {
                    for (let i = 0; i < childs.length; i++) {
                        newArr.push(childs[i]);
                    }
                }
            }
            arr = newArr;
            level++;
        }
    }

    /**
     * 返回节点数量
     * @returns {number}
     */
    nodeCount(node) {
        if (node == null) {
            return 0;
        }
        if (node.childs == null || node.childs.length == 0) {
            return 1;
        }
        let count = 1;
        for (let i = 0; i < node.childs.length; i++) {
            count = count + this.nodeCount(node.childs[i]);
        }
        return count;
    }

    /**
     * 前序遍历
     */
    preOrder(node) {
        if (node == null) {
            return;
        }
        console.log(node.val)
        for (let i = 0; i < node.childs.length; i++) {
            this.preOrder(node.childs[i]);
        }
    }

    /**
     * 中序遍历(只能处理二叉树)
     */
    inOrder(node) {
        if (node == null) {
            return 0;
        }
        if (node.childs != null && node.childs.length > 0) {
            let leftChild = node.childs[0];
            this.inOrder(leftChild)
        }
        console.log(node.val)
        if (node.childs != null && node.childs.length > 1) {
            let rightChild = node.childs[1];
            this.inOrder(rightChild)
        }
    }

    /**
     * 后序遍历
     */
    postOrder(node) {
        if (node == null) {
            return;
        }
        for (let i = 0; i < node.childs.length; i++) {
            this.postOrder(node.childs[i]);
        }
        console.log(node.val)
    }
}

class BinaryTreeNode {
    constructor(val, left, right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }

    isLeaf() {
        if (this.left == null && this.right == null) {
            return true;
        }
        return false;
    }
}

// 二叉树节点
class BinaryTree {
    constructor(node) {
        this.root = node;
    }

    /**
     * 对二叉树进行层序遍历
     * @param root
     */
    levelOrder() {
        if (this.root == null) {
            return;
        }
        let arr = [];
        arr.push(this.root);
        let level = 1;
        let end = 1;
        let start = 0;
        while (start != end) {
            console.log(`第${level}层`)
            for (let i = start; i < end; i++) {
                let node = arr[i];
                console.log(node.val)
                if (node.left != null) {
                    arr.push(node.left);
                }
                if (node.right != null) {
                    arr.push(node.right);
                }
            }
            start = end;
            end = arr.length;
            level++;
        }
    }

    /**
     * 对二叉树进行前序遍历
     * @param node
     */
    preOrder(node) {
        if (node == null) {
            return;
        }
        console.log(node.val)
        if (node.left != null) {
            this.preOrder(node.left)
        }
        if (node.right != null) {
            this.preOrder(node.right)
        }
    }

    /**
     * 对二叉树进行中序遍历
     * @param root
     */
    inOrder(node) {
        if (node == null) {
            return;
        }
        if (node.left != null) {
            this.inOrder(node.left)
        }
        console.log(node.val)
        if (node.right != null) {
            this.inOrder(node.right)
        }
    }

    /**
     * 对二叉树进行后序遍历
     * @param root
     */
    postOrder(node) {
        if (node == null) {
            return;
        }
        if (node.left != null) {
            this.postOrder(node.left)
        }
        if (node.right != null) {
            this.postOrder(node.right)
        }
        console.log(node.val)
    }
}

/**
 * 根节点为索引0.
 */
class ArrayBinaryTree {

    constructor(container) {
        this.arr = container;
    }

    /**
     * 获取索引i的值
     * @param i
     */
    val(i) {
        this.arr[i];
    }

    /**
     * 获取索引为i的左子节点的索引
     * @param i
     */
    left(i) {
        return i * 2 + 1;
    }

    /**
     * 获取索引为i的左子节点的值
     * @param i
     */
    leftVal(i) {
        return val(left(i));
    }

    /**
     * 获取索引为i的右子节点的索引
     * @param i
     */
    right(i) {
        return i * 2 + 2;
    }

    /**
     * 获取索引为i的右子节点的值
     * @param i
     */
    rightVal(i) {
        return val(right(i));
    }

    /**
     * 获取索引为i的父节点
     * @param i
     */
    parent(i) {
        if (i == 0) {
            return -1;
        }
        return Number.parseInt((i - 1) / 2);
    }

    /**
     * 获取索引为i的父节点的值
     * @param i
     */
    parentVal(i) {
        return val(parent(i));
    }

    /**
     * 获取树高
     */
    height() {
        return Number.parseInt(Math.log2(arr.length) + 1);
    }

    /**
     * 层序遍历
     */
    levelOrder() {
        for (let i = 0; i < arr.length; i++) {
            console.log(arr[i]);
        }
    }

    /**
     * 前序遍历
     */
    preOrder(i) {
        console.log(arr[i]);
        this.preOrder(this.left(i));
        this.preOrder(this.right(i));
    }

    /**
     * 后序遍历
     */
    postOrder(i) {
        this.preOrder(this.left(i));
        this.preOrder(this.right(i));
        console.log(arr[i]);
    }

    /**
     * 中序遍历
     */
    inOrder(i) {
        this.preOrder(this.left(i));
        console.log(arr[i]);
        this.preOrder(this.right(i));
    }
}

/**
 * 二叉搜索树
 */
class BinarySearchTree {
    constructor(node) {
        this.root = node;
    }

    /**
     * 添加节点
     * @param node
     */
    add(node) {
        if (this.root == null) {
            this.root = node;
            return
        }
        let findNode = this.findParent(node);
        if (findNode == null) {
            findNode = this.root;
        }
        if (findNode.val > node.val) {
            if (findNode.right == null) {
                findNode.right = node;    
            }
        } else if (findNode.val < node.val) {
            if (findNode.left == null) {
                findNode.left = node;
            }
        }
    }

    /**
     * 删除节点
     * @param node
     */
    remove(node) {
        if (this.root == null) {
            return;
        }
        // 找到父节点
        let parentNode = this.findParent(node);
        if (parentNode == null) {
            this.root = null;
        } else if (parentNode.val > node.val) {
            let right = findNode.right;
            if (right == null) {
                return;
            } else if (right.val != node.val) {
                return;
            }
            // 找到 node 节点
            let removeNode = right;
            this.removeChange(parentNode, removeNode, 'right');
        } else if (parentNode.val < node.val) {
            let left = findNode.left;
            if (left == null) {
                return;
            } else if (left.val != node.val) {
                return;
            }
            let removeNode = left;
            this.removeChange(parentNode, removeNode, 'left');
        }
    }

    /**
     * 移动的节点改变
     * @param parentNode
     * @param removeNode
     * @param propry
     */
    removeChange(parentNode, removeNode, propry) {
        if (removeNode.left != null) {
            // 转接 node节点的左子树
            parentNode[propry] = removeNode.left

            // 转接 node节点的右子树
            let minNode = getMinNode(removeNode.left);
            minNode.right = removeNode.right
            removeNode.left = null;
            removeNode.right = null;
        } else {
            // 转接 node节点的右子树
            parentNode[propry] = removeNode.right
            removeNode.right = null;
        }
    }

    /**
     * 找到某节点的最小节点
     * @param node
     */
    getMinNode(node) {
        let findNode = node;
        while (findNode != null) {
            if (findNode.right != null) {
                findNode = findNode.right;
            } else {
                return findNode;
            }
        }
    }

    /**
     * 找到某节点的最大节点
     * @param node
     */
    getMaxNode(node) {
        let findNode = node;
        while (findNode != null) {
            if (findNode.left != null) {
                findNode = findNode.left;
            } else {
                return findNode;
            }
        }
    }


    /**
     * 查找节点
     * @param node
     */
    find(node) {
        let findNode = this.root;
        while (findNode != null) {
            if (node.val > findNode.val) {
                findNode = findNode.left
            } else if (node.val < findNode.val) {
                findNode = findNode.right
            } else {
                break;
            }
        }
        return findNode;
    }

    /**
     * 查找节点
     * @param node
     */
    findParent(node) {
        let findNode = this.root;
        let parentNode = null;
        while (findNode != null) {
            if (node.val > findNode.val) {
                if (findNode.left != null) {
                    parentNode = findNode;
                    findNode = findNode.left
                } else {
                    return findNode;
                }
            } else if (node.val < findNode.val) {
                if (findNode.right != null) {
                    parentNode = findNode;
                    findNode = findNode.right
                } else {
                    return findNode;
                }
            } else {
                return parentNode;
            }
        }
        return parentNode;
    }
}

class AvlTree {

}

